<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    173. Binary Search Tree Iterator
   </h1>
   <p>
    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
   </p>
   <p>
    Calling
    <code>
     next()
    </code>
    will return the next smallest number in the BST.
   </p>
   <p>
    &nbsp;
   </p>
   <ul>
   </ul>
   <p>
    <strong>
     Example:
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png" style="width: 189px; height: 178px;">
    </strong>
   </p>
   <pre>
BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <b>
     Note:
    </b>
   </p>
   <ul>
    <li>
     <code>
      next()
     </code>
     and
     <code>
      hasNext()
     </code>
     should run in average O(1) time and uses O(
     <i>
      h
     </i>
     ) memory, where
     <i>
      h
     </i>
     is the height of the tree.
    </li>
    <li>
     You may assume that&nbsp;
     <code>
      next()
     </code>
     &nbsp;call&nbsp;will always be valid, that is, there will be at least a next smallest number in the BST when
     <code>
      next()
     </code>
     is called.
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    173. 二叉搜索树迭代器
   </h1>
   <p>
    实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
   </p>
   <p>
    调用
    <code>
     next()
    </code>
    将返回二叉搜索树中的下一个最小的数。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/25/bst-tree.png" style="height: 178px; width: 189px;">
    </strong>
   </p>
   <pre>BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ul>
    <li>
     <code>
      next()
     </code>
     &nbsp;和&nbsp;
     <code>
      hasNext()
     </code>
     &nbsp;操作的时间复杂度是&nbsp;O(1)，并使用&nbsp;O(
     <em>
      h
     </em>
     ) 内存，其中&nbsp;
     <em>
      h&nbsp;
     </em>
     是树的高度。
    </li>
    <li>
     你可以假设&nbsp;
     <code>
      next()
     </code>
     &nbsp;调用总是有效的，也就是说，当调用
     <code>
      next()
     </code>
     &nbsp;时，BST 中至少存在一个下一个最小的数。
    </li>
   </ul>
  </div>
 </body>
</html>